//给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。 
//
// 「超赞子字符串」需满足满足下述两个条件： 
//
// 
// 该字符串是 s 的一个非空子字符串 
// 进行任意次数的字符交换后，该字符串可以变成一个回文字符串 
// 
//
// 
//
// 示例 1： 
//
// 输入：s = "3242415"
//输出：5
//解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
// 
//
// 示例 2： 
//
// 输入：s = "12345678"
//输出：1
// 
//
// 示例 3： 
//
// 输入：s = "213123"
//输出：6
//解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
// 
//
// 示例 4： 
//
// 输入：s = "00"
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10^5 
// s 仅由数字组成 
// 
//
// Related Topics 位运算 哈希表 字符串 👍 133 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-05-20 21:37:44
 * @description 1542.找出最长的超赞子字符串
 */
public class FindLongestAwesomeSubstring{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindLongestAwesomeSubstring fun=new FindLongestAwesomeSubstring();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*用一个二进制的01序列表示前i个数，每个数字出现的奇偶情况
		 * 如01010，表示前i个数中，2.4出现的次数为奇数
		 * 则s[i+1]到s[j]这个j-i长度的子串，每个数字的奇偶性等于s[j]^s[i]
		 * 如果一个子串经过变换后可以变成回文串，如果长度是偶数，则每个数字都应该是偶次，
		 * 或者长度是奇数，且只有一个数字是基数，其余都是偶数即s[j]^s[i]=2^k
		 * 用一个数组单独存储每个前缀异或和出现的位置，
		 * 如p[1101]=5,表示第一个等于1101的前缀异或和下标是5，特别的p[0]=-1
		 * 因为p[-1]=0,*/
	private static final int D=10;//字符串种类
    public int longestAwesome(String s) {
		int n=s.length();
		int [] p=new int[1<<D];
		Arrays.fill(p,n); //n表示没有找到
		p[0]=-1;
		int res=0;
		int pre=0;
		for (int i = 0; i < n; i++) {
			//记录每个位置上的数的奇偶性
			pre^=1<<(s.charAt(i)-'0');
			for (int d = 0; d < D; d++) {
				/*pre^(1<<d)，即如果当前是奇数长度
				且只有一个位置是奇数，如0010^1<<1
				则异或后是0000，
				或者0010出现过了，再次遍历到1010时，
				1010^1<<3,得到0010出现的位置
				 */
				res=Math.max(res,i-p[pre^(1<<d)]); //奇数
			}
			/*
			如果是偶数长度，如0000，则
			 */
			res=Math.max(res,i-p[pre]); //偶数
			if(p[pre]==n){ //首次遇到值为p的前缀异或和，记录其下标i
				p[pre]=i;
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
